package com.gxy.learn.algorithm.sort;

/**
 * @description: 插入排序
 * @author: Gaoxueyong
 * @createDate: 2023/1/9 21:24
 */
public class InsertSort {

    private final static int[] arry = {8, 3, 5, 7, 2, 6, 1, 4};

    public static void main(String[] args) {
        sort(arry);
//        sortNew(arry);
    }

    public static void sort(int[] arry) {
        for (int i = 1; i < arry.length; i++) {
            int preIndex = i - 1;
            int current = arry[i];
            System.out.println("preIndex = " + preIndex);
            System.out.println("current = arry[" + i + "]");
            System.out.println("***************************************");
            while (preIndex >= 0 && arry[preIndex] > current) {
                System.out.println("arry[" + (preIndex + 1) + "] = arry[" + preIndex + "]");
                arry[preIndex + 1] = arry[preIndex];
                preIndex--;
            }
            System.out.println("***************************************");
            System.out.println("arry[" + (preIndex + 1) + "] = current");
            arry[preIndex + 1] = current;
            print(arry, i);
        }
    }


    public static void sortNew(int[] arry) {
        for (int i = 1; i < arry.length; i++) {
            int current = arry[i];
            int j = i;
            while (j > 0 && arry[j - 1] > current) {
                arry[j] = arry[j - 1];
                j--;
            }
//            如果没发生位移则跳过
            if (j == i) {
                continue;
            }
//            如果发生了位移 j肯定不等于i
//            把比较后的值插入到位移后的位置
            arry[j] = current;
            print(arry, i);
        }
    }

    /**
     * 数组打印
     *
     * @param arry  需要打印的数组
     * @param index 第几次打印
     * @return: void
     * @author: Gaoxueyong
     * @time: 2023/1/5 11:18 PM
     */
    static void print(int[] arry, int index) {
        System.out.println(String.format("第[%d]次排序", index));
        for (int num : arry) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
}
